package com.leetcode.LC_MED;

public class LC279_2 {
    // 出错
    int times = Integer.MAX_VALUE;

    private int numSquares(int n) {
        // 对一个数进行开方，将数字的平方存入此数组即可
        int num = (int) Math.sqrt(n);
        int[] res = new int[num];
        int k = 0;
        for (int i = num; i > 0; i--) {
            res[k++] = i * i;
        }
        findRes(n, res, 0, 0);
        return times;
    }

    private void findRes(int n, int[] res, int index, int time) {
        if (n < 0 || index >= res.length) {
            return;
        }
        if (n == 0) {
            times = Math.min(times, time);
            return;
        }
        for (int i = index; i < res.length; i++) {
            if (n % res[i] == 0) {
                times = Math.min(times, time + n / res[i]);
                return;
            }
            if (n / res[i] > 0) {
                time+=n/res[i];
                n=n%res[i];
            }
            if (n - res[i] >= 0) {
                findRes(n - res[i], res, index, time + 1);
            } else {
                findRes(n, res, index + 1, time + 1);
            }
        }
    }

    public static void main(String[] args) {
        LC279_2 lc279_2 = new LC279_2();
        System.out.println(lc279_2.numSquares(69));
    }
}
